package org.alis.smallcc.queen;
/**  
 * All rights Reserved, Designed By www.smalllc.top
 * @Title:  Queen.java   
 * @Package com.lc.sort   
 * @Description:   经典回溯算法 八皇后问题  
 * @author: 晓风过境  
 * @date:   2018年5月13日 上午12:50:48   
 * @version V1.0 
 * @Copyright: 2018 
 */ 
public class Queen {
	public static int num=0;//累积方案
	public static final int MAXQUEEN=8;
	public static int[] cols=new int[MAXQUEEN];//定义Cols数组，表示8列棋子皇后最后摆放的位置
	
	public void getCount(int n) {
		boolean[] rows=new boolean[MAXQUEEN];//记录每列每个方格是否可以放置皇后
		for(int m=0;m<n;m++) {
			rows[cols[m]]=true;//先初始横列
			int d=n-m;//斜对角
			//正斜方向
			if(cols[m]-d>=0) {
				rows[cols[m]-d]=true;
			}
			//反斜方向
			if(cols[m]+d<=MAXQUEEN-1) {
				rows[cols[m]+d]=true;
			}
		}
		//到此就知道哪些位置不能摆放皇后了
		for(int i=0;i<MAXQUEEN;i++) {
			if(rows[i]) {
				//不能放
				continue;
			}
			cols[n]=i;
			if(n<MAXQUEEN-1) {
				getCount(n+1);
			}else {
				//找到完整的一套方案
				num++;
				printQueen();
			}
			//下面可能仍然有合适的位置摆放
		}
	}

	private void printQueen() {
		System.out.println("第"+num+"种方案");
		for(int i = 0;i<MAXQUEEN;i++){
			for(int j = 0;j<MAXQUEEN;j++){
				if(i == cols[j]){
					System.out.print("0 ");
				}else{
					System.out.print("+ ");
				}
			}
			System.out.println();
		}	
	}
	public static void main(String[] args) {
		Queen queen=new Queen();
		queen.getCount(0);
	}
}
